/*
 【基础】快速幂 - JOYSKID
  题目描述
    求 x^p mod m 的值。
    提示：
      若 p 为偶数，x^p = ( x^(p/2) )^2;
      若 p 为奇数，x^p = ( x^((p-1)/2) )^2;
      该题可以采用分治法求解。
  输入格式
    三个不超过 int 的正整数 x, p, m。
  输出格式
    参考样例。
  输入数据 1
    2 10 100
  输出数据 1
    2^10 mod 100=24
*/

#include <bits/stdc++.h>

using namespace std;

int x, p, m;

/*
  使用分治的方法求 x^p mod m 的值
  注意: 使用分治的方法进行编码时，通常会用到递归!
*/
long long f(int x, int p, int m) {
    if (p == 1) {
        return x % m;
    } else if (p % 2 == 0) {
        long long sum = f(x, p / 2, m);
        return (sum * sum) % m;
    } else {
        long long sum = f(x, p / 2, m);
        return (sum * sum % m)* x % m; // 注意: 为了避免因数据过大超过变量的最大值而损失精度，
                                       //       每 2 个 int类型的数相乘后，并在进行下一次乘法操作前，
                                       //       需立即对结果进行求余操作!
    }
}

int main() {
    cin >> x >> p >> m;
    cout << x << "^" << p << " mod " << m << "="<< f(x, p, m);

    return 0;
}